/*
https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/solution/cai-shu-zi-da-xiao-ii-by-leetcode-soluti-a7vg/
 */
public class Solution375 {
    public int getMoneyAmount(int n) {
        int[][] f=new int[n+1][n+1];
        return search(1,n,f);
    }
    int search(int i,int j,int[][] f){
        if (i>=j) return 0;
        if (f[i][j]!=0){
            return f[i][j];
        }
        int ans=Integer.MAX_VALUE;
        for (int k=i;k<=j;k++){
            ans=Integer.min(k+Math.max(search(i,k-1,f),search(k+1,j,f)),ans);
        }
        f[i][j]=ans;
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution375().getMoneyAmount(10));
    }
}
